Local Area Networks (LANs) connect computing systems together. LANs of all types can be connected together using Media Access Control (MAC) bridges, as set forth in the “IEEE Standard for Information Technology, Telecommunications and Information Exchange between Systems, Local and Metropolitan Area Networks, Common Specifications, Part 3: Media Access Control (MAC) Bridges,” published as ANSI/IEEE Standard 802.1D (1998), which is incorporated herein by reference. The 802.1D standard is available at standards.ieee.org/catalog/IEEE802.1.html. Each computing system connects to a LAN through a MAC device. MAC bridges that implement the 802.1D standard allow MAC devices attached to separate LANs to appear to each other as if they were attached to a single LAN.
The most common type of MAC bridge is a switch, which has multiple ports connecting it to LANs, other switches, host computing systems, or other network elements. Switches can be roughly classified as access switches or core switches. An access switch has ports that connect to LANs and/or to other network endpoints, such as user computer systems. Core switches interconnect the access switches into a Wide Area Network (WAN), by direct connection between the core switch and access switches and/or by connection to other core switches. Core switches that are directly connected to access switches are referred to herein as edge switches.
When a switch receives a data frame on one of its ports, it examines the destination MAC address carried in the frame header to determine through which of its output ports the frame should be transmitted. For this purpose, in accordance with the above-mentioned 802.1D standard, the switch maintains a filtering database, indicating the appropriate destination port for each MAC address in the database. The switch ports use the filtering database as a lookup table (LUT) for forwarding frames that they receive. When the switch receives a frame on one of its ports from a particular source MAC address, it “learns” to associate that MAC address with that port and places a corresponding entry in its filtering database. When the switch receives a frame with a destination address that does not appear in its database, it “floods,” or broadcasts, the frame through all its ports except the port on which the frame was received. Broadcast and multicast frames are similarly distributed by flooding. On the other hand, when the switch finds that the destination address of a frame received on one of its ports is associated in its database with that same port, it discards, or “filters,” the frame.
As the switch receives packets, it continually adds entries to its filtering database. In order to avoid filling up the database with stale entries and to enable the database to be updated when changes occur in network topology, the 802.1D standard defines an aging mechanism. When an entry is created in the table due to a frame having been received from a particular source MAC address, the entry receives a time stamp. Whenever another frame is received from the same address (on the same port), the time stamp is updated. If the time stamp is not updated within a predetermined time limit, the entry is erased. The default aging time is five minutes. Because of this long aging time, it can take a long time to rebuild the filtering database after a network topology change.
To protect against failures of network equipment and communication media, it is common to provide multiple, redundant paths between switches in the network. For example, access switches are typically connected to edge switches by dual links. These links may be in the form of connections between each of a pair of ports on one access switch with a corresponding pair of ports on the edge switch. Alternatively, each of two access switches may be connected to one of the ports of the edge switch, with an additional link provided between the two access switches. Other redundant protection configurations are also known in the art. All these configurations are meant to ensure the connection between the access switch (or switches) and the edge switch will be maintained even if there is a failure in one of the ports or in the associated media connecting the edge switch and access switches.
A problem with redundant topologies, however, is that the multiple paths between points in the network can create loops that disrupt the proper functioning of the learning process described above. Furthermore, broadcast packets may be forwarded repeatedly by the switches in the loop, causing a serious problem of network congestion, known as a “broadcast storm.”
In order to avoid these problems, the 802.1D standard defines a communication protocol, known as the spanning tree protocol (STP), for managing the creation and updating of the network topology. STP ensures that all data paths in a network of bridges are free of loops by disabling forwarding of packets through certain interfaces. The spanning tree algorithm takes advantage of a standard feature of MAC ports: the ports may be either in a blocking state or a forwarding state. Frames are forwarded through ports in a MAC bridge in the forwarding state, and not through ports in the blocking state. At any time, a given bridge effectively connects only the LANs that are attached to those of the bridge ports that are in a forwarding state. Ports that are in a blocking state do not forward frames. The spanning tree algorithm and protocol thus create a tree-shaped active topology from the arbitrarily-connected components of the network.
The spanning tree algorithm defines one bridge in the network as the root bridge. Each LAN connected to the network has a bridge port that connects it to the root bridge. The port is known as the designated port for the LAN, and the bridge of which the designated port is part is known as the designated bridge for the LAN. The root bridge is the designated bridge for each LAN to which it is connected. Each bridge has a port defined as its root port, which uniquely connects that bridge to the root bridge. All ports on the bridge that are neither the root port nor the designated port are put into the blocking state. Frames destined to cross the network will thus travel from the designated bridge of the originating LAN along a root path toward the root bridge. If the destination bridge does not lie along the root path, the frame will be routed through the root bridge and will travel along a root path from the root bridge to the designated port for the destination LAN.
Although STP is effective in removing network loops, it is very slow in adapting to topology changes that may occur when a network link fails or is subsequently restored. Responding to a failure typically necessitates recalculating the spanning tree to accommodate the topology change and accordingly transferring bridge ports from the blocking to the forwarding state. The above-mentioned 802.1D standard specifies a procedure for responding to topology changes, which includes reducing the aging time for filtering database entries to 15 sec. Using this procedure with default STP timing parameters (as specified in the above-mentioned 802.1D standard), it still takes 30 sec to transfer ports from the blocking state to the forwarding state. Even with aggressive tuning of the timing, the transfer from blocking to forwarding state takes at least 14 sec, and it generally takes as much as a minute overall for normal network service to be restored.
U.S. Pat. No. 6,032,194, whose disclosure is incorporated herein by reference, describes a method for rapidly reconfiguring a computer network, based on certain modifications to the standard STP. The method assumes that the switches in the network, including both core and access switches, have multiple trunk ports providing connectivity to the STP root via trunk switches. (These trunk switches are comparable to the core switches and edge switches defined above, and the trunk ports are on the upstream side of each switch, i.e., the side leading toward the root.) One of the trunk ports of each switch is placed in the forwarding state, while the others are designated as back-up ports. Upon detection of a failure at the active forwarding port, the switch immediately places one of the back-up trunk ports in the forwarding state, so that it becomes the new active port. The switch then transmits dummy multicast messages toward the root (upstream) through the newly-active trunk port, each containing the source address of a network entity that is coupled to the switch itself or is downstream of the switch. Upon receiving these messages, other devices in the network learn to use the new active port. In order to implement this rapid reconfiguration method, special commands, not a part of the 802.1D standard, are used to modify the STP parameters of both the core switches and the access switches in the network. The patent also suggests modifications to these special commands for operating in a Virtual LAN (VLAN) environment.
A similar rapid reconfiguration algorithm is defined in a draft amendment to the 802.1D standard, entitled “Amendment 2—Rapid Reconfiguration,” published as IEEE Draft P802.1w/D10 (Mar. 26, 2001), which is incorporated herein by reference. This draft specifies enhancements to the operation of STP and other mechanisms that support reconfiguration of physical and filtering connectivity in a bridged LAN system. Implementation of the enhanced protocol substantially reduces the time required to recompute the spanning tree and reconfigure switch ports and filtering databases following a network topology change. But it requires that all the switches in the network be replaced or reprogrammed to comply with the amended standard.